/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>
#include <memory/vaddr.h>

enum {
  TK_NOTYPE = 256, TK_EQ,TK_NEQ,TK_REG,TK_LB,TK_RB,
  TK_NUM,TK_NUM_HEX,TK_AND,TK_MEM
  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"-", '-'},         // min
  {"\\*", '*'},         // mul
  {"/", '/'},         // div
  {"0x[0-9A-Fa-f]+",TK_NUM_HEX}, //hex num
  {"[0-9]+",TK_NUM}, //dec num
  {"==", TK_EQ},        // equal
  {"!=", TK_NEQ},
  {"&&",TK_AND},
  {"\\$[\\$a-z0-9PC]+",TK_REG},
  {"\\(",TK_LB},
  {"\\)",TK_RB},
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[3200] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        // Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            // i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        if(substr_len > 32) {
          printf("%s str's len is over 32. len:%d\n",substr_start,substr_len);
          break;
        }
        memcpy(tokens[nr_token].str,substr_start,substr_len);
        tokens[nr_token].str[substr_len] = 0;
        tokens[nr_token].type = rules[i].token_type;

        switch (rules[i].token_type) {
          case '*':
            /*The first operator * can't be multiply.*/
            if(nr_token == 0) {
              tokens[nr_token].type = TK_MEM;
              break;
            }
            int last_type = tokens[nr_token-1].type;
            /*When the last token is number or the right bracket, this operator * means the multiply.*/
            if(last_type == TK_NUM || last_type == TK_NUM_HEX || last_type == TK_REG || last_type == TK_RB){
              tokens[nr_token].type = '*';
            } else {
              tokens[nr_token].type = TK_MEM;
            }
            break;
          default: break;
        }
        nr_token++;
        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

/*Search the operator prioity, larger is higher.*/
static int op_prio(int token_type) {
  int ret = 0;
  switch(token_type) {
    case TK_LB: ret = 5; break;
    case TK_RB: ret = 5; break;
    case '+': ret = 10; break;
    case '-': ret = 10; break;
    case '*': ret = 20; break;
    case '/': ret = 20; break;

    case TK_NEQ: ret = 7; break;
    case TK_EQ:  ret = 7; break;
    case TK_AND: ret = 8; break;
    case TK_MEM: ret = 30; break;
  }
  return ret;
}

static bool expr_abort = false;
word_t eval_word(Token *token) {
  word_t ret = 0;
  if(token->type == TK_NUM) {
    ret = atol(token->str);
  } else if(token->type == TK_NUM_HEX) {
    int pos = 2; /*skip the prefix '0x'*/
    while(pos < 32 && token->str[pos] != 0) {
      int c = token->str[pos];
      if(c >= 'a' && c <= 'f') c -= 'a' - 10;
      else if(c >= 'A' && c <= 'F') c -= 'F' - 10;
      else if(c >= '0' && c <= '9') c -= '0';
      ret *= 16;
      ret += c;
      pos++;
    }
  } else if(token->type == TK_REG) {
    bool success = false;
    ret = isa_reg_str2val(token->str+1,&success);
    if(success == false) expr_abort = true;
  }
  return ret;
}

static Token token_stack[3200];
static int token_top = -1;

static Token suffix_expr[3200];
static int nr_suffix_expr = 0;

static word_t get_op_value(int cnt) {
  word_t value1,value2,res = 0;
    switch(suffix_expr[cnt].type) {
      case '+': 
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        res = value1 + value2;
        break;
      case '-': 
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        res = value1 - value2;
        break;
      case '*': 
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        res = value1 * value2;
        break;
      case '/': 
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        if(value2 == 0) {
          expr_abort = true;
          printf("divde number is 0\n");
          return -1;
        }
        res = value1 / value2; 
        break;
      case TK_NEQ: 
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        res = value1 != value2; 
        break;
      case TK_EQ:  
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        res = value1 == value2; 
        break;
      case TK_AND: 
        value1 = eval_word(&suffix_expr[cnt-2]);
        value2 = eval_word(&suffix_expr[cnt-1]);
        res = value1 && value2; 
        break;
      case TK_MEM: 
        value1 = eval_word(&suffix_expr[cnt-1]);
        res = vaddr_read(value1,sizeof(word_t)); 
        break;
      case TK_REG:
        break;
    }
    return res;
}
word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  /* TODO: Insert codes to evaluate the expression. */
  // TODO();
  nr_suffix_expr = 0;
  token_top = -1;
  expr_abort = false;
  int i;
  for (i = 0; i < nr_token; i++) {
    int type = tokens[i].type;
    if(type == TK_NUM || type == TK_NUM_HEX|| type == TK_REG) { /*If token is number,push it into result stack directly.*/
      suffix_expr[nr_suffix_expr] = tokens[i];
      nr_suffix_expr++;
    } else if(type == TK_RB) { /*If token is right bracket, pop operator until left bracket.*/
      while(token_top != -1 && token_stack[token_top].type != TK_LB) {
        suffix_expr[nr_suffix_expr] = token_stack[token_top];
        nr_suffix_expr++;
        token_top--;
        int top_type = suffix_expr[nr_suffix_expr-1].type;
        if(top_type == '+' || top_type == '-' || top_type == '*' || top_type == '/' ||
          top_type == TK_EQ || top_type == TK_NEQ || top_type == TK_AND || top_type == TK_MEM ) {
          word_t val = get_op_value(nr_suffix_expr - 1);
          if(expr_abort == true) return 0;
          if(top_type == TK_MEM ) nr_suffix_expr -= 1;
          // else if(top_type == TK_REG) nr_suffix_expr -= 0;
          else nr_suffix_expr -= 2;
          suffix_expr[nr_suffix_expr-1].type = TK_NUM;
          sprintf(suffix_expr[nr_suffix_expr-1].str,"%ld",val);
        }

      }
      /*Remove the top operator '('.*/
      token_top--;
    } else if(type == TK_LB) {
      token_top++;
      token_stack[token_top] = tokens[i];
    } else {
      int top_prio = 0;
      if(token_top != -1) top_prio = op_prio(token_stack[token_top].type);
      int prio = op_prio(tokens[i].type);
      if(prio > top_prio) {
        token_top++;
        token_stack[token_top] = tokens[i];
      } else {
        while(prio <= top_prio && token_top != -1) {
          suffix_expr[nr_suffix_expr] = token_stack[token_top];
          nr_suffix_expr++;
          token_top--;
          top_prio = op_prio(token_stack[token_top].type);

          int top_type = suffix_expr[nr_suffix_expr-1].type;
          // printf("op type:%d - %c\n",top_type,top_type);
          if(top_type == '+' || top_type == '-' || top_type == '*' || top_type == '/' ||
             top_type == TK_EQ || top_type == TK_NEQ || top_type == TK_AND || top_type == TK_MEM ) {
            word_t val = get_op_value(nr_suffix_expr - 1);
            if(expr_abort == true) return 0;
            if(top_type == TK_MEM) nr_suffix_expr -= 1;
          // else if(top_type == TK_REG) nr_suffix_expr -= 0;
            else nr_suffix_expr -= 2;
          // printf("op type:%d - %c\n",suffix_expr[nr_suffix_expr-1].type,suffix_expr[nr_suffix_expr-1].type);
            suffix_expr[nr_suffix_expr-1].type = TK_NUM;
            sprintf(suffix_expr[nr_suffix_expr-1].str,"%ld",val);
          }
        }

        token_top++;
        token_stack[token_top] = tokens[i];
      }
    }
  }

  /* print the suffix expr */
  // for (int cnt = 0; cnt < nr_suffix_expr; ++cnt) {
  //   printf("%s ",suffix_expr[cnt].str);
  // }
  // printf("\n");

  // for (int cnt = 0; cnt <= token_top; ++cnt) {
  //   printf("%s ",token_stack[cnt].str);
      
  // }
  // printf("\n");

  while(token_top >= 0) {
    suffix_expr[nr_suffix_expr] = token_stack[token_top];
    nr_suffix_expr++;
    token_top--;    

    int top_type = suffix_expr[nr_suffix_expr-1].type;
    if(top_type == '+' || top_type == '-' || top_type == '*' || top_type == '/' ||
      top_type == TK_EQ || top_type == TK_NEQ || top_type == TK_AND || top_type == TK_MEM ) {
      word_t val = get_op_value(nr_suffix_expr - 1);
      // printf("%ld %s\n",val,expr_abort?"true":"false");
      if(expr_abort == true) return 0;
      if(top_type == TK_MEM) nr_suffix_expr -= 1;
      // else if(top_type == TK_REG) nr_suffix_expr -= 0;
      else nr_suffix_expr -= 2;
      suffix_expr[nr_suffix_expr-1].type = TK_NUM;
      sprintf(suffix_expr[nr_suffix_expr-1].str,"%ld",val);
    }
  }

  // /* print the suffix expr */
  // for (int cnt = 0; cnt < nr_suffix_expr; ++cnt) {
  //   printf("%s ",suffix_expr[cnt].str);
  // }
  // printf("\n");
  if(suffix_expr[0].type == TK_NUM || suffix_expr[0].type == TK_NUM_HEX || suffix_expr[0].type == TK_REG) {
    *success = true;
    return eval_word(&suffix_expr[0]);
  }
  

  return 0;
}
